package algorithm_demo.sort;

import java.util.Arrays;

/**
 * 基数排序
 *
 * @author Api
 * @date 2022/11/20 12:27
 */
public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {8, 22, 34, 1, 3, 2, 12, 12, 3, 4, 54, 53};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void radixSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxBits(arr));
    }


    public static int maxBits(int[] arr) {
        int max = Integer.MIN_VALUE;

        for (int j : arr) {
            max = Math.max(max, j);
        }

        int res = 0;
        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

    /**
     * @param arr
     * @param L
     * @param R
     * @param digit 表示这批数字中有几个十进制位
     */
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10;
        int i, j;
        //有多少个数准备多少个辅助空间。
        //辅助数组，和原数组等规模数组
        int[] bucket = new int[R - L + 1];
        for (int d = 1; d <= digit; d++) {//有多少位就进出几次
            //10个空间
            //count[0] 当前位（d位）是0的数字有多少个
            //count[1] 当前位（d位）是（0和1）的数字有多少个
            //count[2] 当前位（d位）是（0、1和2）的数字有多少个
            //count[i] 当前位（d位）是（0-i）的数字有多少个
            int[] count = new int[radix]; // count[0-9]
            //count词频统计
            for (i = L; i <= R; i++) {
                j = getDigit(arr[i], d);
                count[j]++;
            }
            //将count词频转换为前缀和数组，也就是比如个位数字<=2有多少个，累加和
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }
            //从右往左遍历，先入桶的先出桶了
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], d);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }

            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }
    public static int getDigit(int x, int d) {
        return ((x / ((int) Math.pow(10, d - 1))) % 10);
    }
}
